
class Solution1 {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int[][] dp = new int[n + 1][sum + 1];
        for (int j = 1; j <= sum / 2; j++) {
            dp[0][j] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum / 2; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != -1) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] + nums[i - 1];
                }
            }
        }

        return dp[n][sum / 2] != -1;
    }
}


class Solution2 {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int aim = sum / 2;
        boolean[][] dp = new boolean[n + 1][aim + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= aim; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]]) dp[i][j] = true;
            }
        }

        return dp[n][aim];
    }
}


class Solution3 {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int aim = sum / 2;
        boolean[] dp = new boolean[aim + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i - 1]; j--) {
                if (dp[j - nums[i - 1]]) {
                    dp[j] = true;
                }
            }
        }

        return dp[aim];
    }
}
// a+b = sums;
// a-b = target
// a - sums + a = target
// 2a = target + sums
// a = target+sums/2

class Solution4 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0, n = nums.length;
        for(int x:nums) {
            sum += x;
        }

        int aim = (target + sum)/2;
        if((target + sum)%2 == 1 || aim < 0) return 0;

        int[][] dp = new int[n+1][aim+1];
        dp[0][0] = 1;
        for(int i = 1; i<=n; i++) {
            for(int j = 0; j<=aim; j++) {
                dp[i][j] += dp[i-1][j];
                if(j >= nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }

        return dp[n][aim];
    }
}

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length, sum = 0;
        for(int x:stones) sum += x;
        int aim = sum/2;
        int[][] dp = new int[n+1][aim+1];
        for(int i =1; i<=n; i++) {
            for(int j = 1; j<=aim; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= stones[i-1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-stones[i-1]] + stones[i-1]);
                }
            }
        }
        System.out.println(sum + " " + dp[n][aim]);

        int ans = Math.abs(dp[n][aim] - (sum - dp[n][aim]));
        return ans;
    }
}


public class Test {
}
